package org.algorithm.biubiu.wheel_1.数组.三月.第四周;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:32 PM
 * @description:  周四作业
 *
 *
 * url :  https://leetcode-cn.com/problems/n-queens/
 */
public class N皇后 {

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }


    public static List<List<String>> solveNQueens(int n){


        List<List<String>> res =new ArrayList<>();
        search(res,new ArrayList<Integer>(),n);
        return res;
    }

    private static void search(List<List<String>> res, ArrayList<Integer> columns, int n) {
        if(columns.size()==n){
            res.add(build(columns));
            return ;
        }
        for(int x=0;x<n;x++){
            if(!validate(columns,x)){
                continue;
            }
            columns.add(x);
            search(res,columns,n);
            columns.remove(columns.size()-1);
        }
    }

    private static List<String> build(ArrayList<Integer> columns) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < columns.size(); i++) {
            StringBuilder stringbuilder = new StringBuilder();
            for (int j = 0; j <columns.size(); j++) {
                stringbuilder.append(i  == columns.get(j)?"Q":"." );
            }
            res.add(stringbuilder.toString());
        }
        return res;
    }

    private static boolean validate(ArrayList<Integer> columns, int x) {
        int y = columns.size();
        for(int yIndex =0 ;yIndex<columns.size();yIndex++){
            // 上一层 坐标 X轴 xindex = colum.get(xIndex)  Y轴 yIndex
            //下一层  坐标 X轴   x                         Y轴 nextY
            int xIndex = columns.get(yIndex);
            if(xIndex == x){
                return false;
            }
            if(y-x == yIndex-xIndex){
                return false;
            }
            if(x+y==xIndex + yIndex){
                return false;
            }
        }
        return true;
    }


}
